1. Possibly Relevant Patents
A search of the patent literature returned the following U.S. patents, as well as the coowned patents mentioned earlier. U.S. Pat. Nos.
5,331,440 Kita PA1 5,425,134 Ishida PA1 5,719,956 Ogatsu PA1 5,737,453 Ostromoukhov PA1 5,739,917 Shu PA1 5,742,405 Spaulding PA1 5,805,178 Silverbrook PA1 5,809,181 Metcalfe PA1 5,857,063 Poe. PA1 a device state composed of only one drop of cyan or magenta, if a cyan color value in the fine-resolution color value exceeds or equals a magenta color value in the fine-resolution color value, and PA1 otherwise selecting another device state composed of only one drop of magenta or cyan respectively.
Of these, as will be seen the most relevant appears to be U.S. Pat. No. 5,739,917, issued to Joseph Shu of Seiko Epson.
2. Approximating a Color Continuum with a Limited Number of Discrete Colors
Photograph-like pictures are generally displayed on computer screens using "twenty-four-bit color"--a phrase which refers to eight bits for each of the additive primary colors red, green and blue. For each primary color the eight bits provide 2.sup.8 =256 possible levels, ranging from none of the specified color to full saturation of that color.
Of course not all colors are primaries, but the computer screen can show combinations of any level of each of the three primaries. Therefore the number of possible colors that can be displayed in any single pixel is 256.sup.3, which comes to nearly seventeen million discrete colors.
Unfortunately most incremental printers--inkjet, or xerographic printers, for example--have a much smaller set of actually printable colorants. The simplest and best known of these devices is binary and usually provides the three subtractive primary colors cyan, magenta and yellow--plus black. The number of discrete colors that can be printed with such a unit is therefore only 2.sup.4 =16 colors within a single pixel.
Some more-modern devices, however, instead have two different dilutions of some of the colorants--usually of magenta and of cyan, and sometimes of black. Furthermore, these devices may be able to provide varying numbers of inkdrops (or other quanta) of the colorants, for instance from zero to four drops of each of the different colorants in their different dilutions.
As a result, the number of discrete colorant combinations that can be produced within any single pixel may be, say, into the thousands. Even these numbers are obviously far smaller than seventeen million. As a practical matter furthermore, many of these combinations are very close to one another and hence essentially redundant--so there are not really as many discrete colors as there are of colorant combinations. Moreover many of the combinations are best forbidden because they would deposit too many drops of ink (too much liquid) in a single pixel.
Consequently, as will be seen later, the number of practically useful discrete colorant combinations may be roughly one hundred twenty-five. How can a 16-color or 125-color machine (or even a thousand-color machine) make colors that look like the colors in an original picture, if the original was able to use any of seventeen million colors?
What is usually done is to trade off some spatial resolution (very small pixels) for "color space" resolution. In other words, some of the printer's capability to produce extremely fine detail is sacrificed, and the system averages the available colors over some relatively large number of pixels.
The system accepts coarser resolution within the two-dimensional positional space of the image to obtain finer resolution within abstract color space. In this way, much finer color gradations are obtained.
The number of pixels used in the averaging process determines how close to 17 million colors the printer can get. One way in which this tradeoff is done is called "dithering".
Dithering is not closely relevant to the present invention. In the dithering approach a fixed, well-defined, usually rectangular cell of pixels (generally between two and thirty-two pixels) is used to produce a kind of color averaging within the cell. Although dithering works well for commercial graphics and other images that contain extended fields of uniform color, it has a tendency to generate within the image spurious visible patterning that is not usually acceptable for photograph-like images.
For photos, therefore, most workers prefer a different approach called "error diffusion". This system evaluates the original twenty-four-bit input color in a specific pixel to see what color available in the machine (for instance, which one of the one hundred twenty-five discrete colors that a machine can make in a single pixel) is closest to that input color.
Then the printer selects to print, and actually prints, that closest input color in the specific pixel--but it also evaluates the error in the printed color. This error is then distributed to several nearby pixels that have not yet been processed.
When the system later reaches one of those pixels, for processing, it adds to the input color in that pixel the previously allocated error from earlier-processed pixels--before making the assessment and printing decision mentioned above. In this way error is continuously propagated from pixel to pixel, and so is diffused, analogously to some component liquid in a continuous-dilution process in a liquid stream.
3. Basics of Underlying Device-State System
The present inventors' above-mentioned prior patent document advances the art of multiple-ink error diffusion by defining so-called "device states". This is where the one hundred twenty-five discrete colors come from--they are carefully precalculated and refined to provide an ideal "palette" of basic colors from which good approximations to all colors can be error-diffusion generated.
The device states, or palette colors, are worked out so that they not only provide an excellent source of colors for use in combinations but also are optimized in terms of the amount of liquid going into each pixel. The system of the related patent application operates very quickly and efficiently, based upon a lookup-table (LUT) approach in which not only the target device state but also the corresponding error is found in the table, thereby saving much computational time.
Thus the LUT has several thousand "major entries" from which to funnel down to the one hundred twenty-five available device states. The related patent application also introduces other procedural features that are significant overall but not important to the now-desired patent search.
4. The Printing of Grays; Black Replacement and Undercolor Substitution
An important and difficult aspect of color printing by almost any methodology is the selection of colorants for reproducing gray and near-gray constituents of colors, to produce best image quality--and particularly quality in highlight areas. First, grays and near grays may be regarded as dilutions of "black".
There are two principal ways to print black, whether in incremental printing or in older-fashioned printing-press systems: "single color" black, using real black ink, and "process black" which is produced as a common quantity of the three subtractive primaries cyan, magenta and yellow.
It is well known that in many situations it is desirable to substitute real black ink for a common fraction of the three subtractive primaries that may happen to be present in a particular desired color. This is a desirable thing to do in midtone regions of an image and also in shadow regions--because it consumes less ink, and puts less liquid onto the print medium, and for many people the single-color black looks blacker than the process black.
On the other hand, it is also known that in many situations it is desirable to go the other way--i. e. to substitute adjacent dots of the three subtractive primaries for real black. This is a desirable thing to do in the interest of obtaining a richer, deeper black (though perhaps not as "accurate" a black) in the midtone to lighter regions of an image--but more importantly in highlight regions, where the isolated dots of real black ink produce an excessively grainy appearance.
More specifically, when a desired shade of gray is very light, if the printer is to render such a shade purely in black ink, the printer is called upon to produce only a relatively few widely scattered or separated black dots--each of which is, at least in theory, dead black. This is the reason for the objectionable graininess.
The equivalent gray shade produced by adjacent or even partly overlapping dots of magenta, cyan and yellow is significantly more diffuse in appearance because, first, the individual dots are each lighter than the black dots would be; and second, the subtractive-secondary dots occupy a larger fraction of the space in the gray area.
By virtue of these two effects in combination, the gray tone is more diffusely distributed and hence less grainy. For present purposes, because yellow dots are much lighter than magenta and cyan dots, the yellow dots can be disregarded--and FIG. 12 can be seen as an approximation to the substitution of overlapping cyan and magenta dots for black-ink dots.
This prior-art technique does produce some improvement (increase) in overall diffuseness of the colorants and reduction of graininess. FIG. 12 does at the same time suggest, however, that the colorants (particularly the darker magenta and cyan) still remain very strongly clumped together--i. e. overlapping or even overprinted.
5. Known Highlight-Graininess Improvements in the Art: The Shu Patent
FIG. 13 illustrates a more definite improvement that appears in the prior art. The point is to ameliorate the graininess remaining in FIG. 12 by avoiding overlap while still holding the magenta and cyan in close association.
This is the solution offered in the previously mentioned Shu patent. Shu's abstract gives the general idea rather well, and this is echoed at column 6, lines 23 through 47.
The passage that appears most relevant to the present invention runs from column 6, line 47, through column 7 line 3. Shu's algorithm tries to avoid overlap of dots whenever possible, leading to dot positioning as suggested in FIG. 13.
Although there is no overlap of cyan and magenta dots, magenta dots are likely to appear next to cyan dots (column 6, line 61)--even when there is ample space between any two cyan dots. As a result each pair of coupled cyan and magenta dots will look like a large dark dot from typical viewing distance.
Although this result is somewhat better than overlapping the two dots of each pair, the granularity of the printed region is still high. The Shu patent, moreover, does not describe a device-state system.
Shu's approach operates by varying a threshold that depends on a relationship between the different color signals at each pixel of interest. As will be seen after introduction of the present invention, such a threshold-based algorithm is relatively awkward and inefficient. (The term "inefficient" is in effect a synonym for "slow", but making allowance for differences in time per processor operation for different types of computing equipment.)
In addition, although he says that he is concerned about making light colors look smoother, Shu's technique is not aimed at highlight regions in particular. Instead it is applied at rather high values of the CMY color signals, and analysis of his functional descriptions seems to suggest that he is most concerned about middle tones.
Perhaps the most interesting aspect of Shu's invention is the way in which it controls deposition of cyan and magenta after a decision to print either one of those two inks in a given pixel. In particular, referring to the other of those two inks, Shu says that his invention increases the "likelihood that ink will be deposited in neighboring pixels".
For example, if Shu's system has decided to print magenta in a particular pixel, then his system will increase the probability of printing cyan in neighboring pixels. Conversely, if Shu's system has decided to print cyan in a particular pixel, then the system will increase the probability of printing magenta in neighboring pixels.
This is precisely the reason for the result diagramed in FIG. 13 of the present document, which shows cyan and magenta dots C, M clustered closely--though concededly they are in separate pixels. For purposes of the present invention the graininess of such an inking pattern is considered unacceptable, or at least undesirable.
The graininess seen in such a scattering of even cyan and magenta dots, in close proximity to one another, somewhat approaches the graininess of black dots. This is true because these two colorants are the darker two constituents of process black.
Of course it is not as grainy as black-ink dots. Yet in a highlight or near-yellow region it is conspicuous and artificial-looking, certainly upon close inspection, and so remains objectionable.
The previously identified copending patent document addressed to "correlating Cyan and Magenta Planes" takes an approach that is conceptually somewhat related to Shu's system--and operates on-the-fly, which is relatively less efficient in comparison with a precalculated LUT approach. It is also somewhat related to the present invention, particularly in that it operates in the context of an error-diffusion system--and it achieves a result better than Shu's.
6. Known Improvements: The Poe Patent
The previously mentioned Poe patent teaches the use of generalized transforms that facilitate establishment of essentially any desired relationship--including arbitrary relationships--between colorants. Poe particularly addresses highlight regions, and particularly with regard to gray or near-gray colors.
As such, Poe's invention is extremely powerful. Poe, however, does not appear to teach a specific methodology for diminishing granularity--i. e. improving the diffuseness--beyond what is shown by, for example, Shu.
Moreover, Poe's teachings are not evidently directed to device-state systems. In addition, if his patented algorithm is applied to, for example, continuous dye-transfer printing, his job is done.
In inkjet printing, however, because the capability of a printhead to deliver ink is quantized--say, 10 pL per drop--it is necessary to use a halftone process to determine how many drops of CMYK ink are needed on each pixel. Poe's methodologies do not appear to extend this far; representatively the output of his algorithm is printer KCMY, which is twenty-four bits or continuous value and not yet halftoned.
7. Known Improvements: The Spaulding Patent
The previously mentioned Spaulding patent, like that of Shu, describes a system that operates on a threshold basis. Spaulding calculates a method of defining thresholds in multilevel halftoning, with the objective of creating output tones that are "approximately linear with perceived lightness".
Spaulding proceeds on a one-dimensional basis and treats CMY separately. This procedure, like threshold processing, is relatively cumbersome and inefficient.
Moreover, for each incoming CMY signal Spaulding's process always selects the ink state with minimum error defined as dC+dM+dY--that is, the algebraic sum of the individual errors dC, dM, dY in the three chromatic planes C, M, Y. In this regard Spaulding goes astray, since the true error distance in three-dimensional color space is instead the root sum square, i. e. the square root of (dC).sup.2 +(dM).sup.2 +(dY).sup.2.
8. Details of Underlying Device-State System
As noted above, a device-state error-diffusion algorithm uses a precalculated error-diffusion table to determine which ink combination to use and how the error is distributed. The device-state system thus inherently provides a built-in capability that can be exploited, simply by changing the table, to provide color performance originally not specifically intended.
Such changes in image character sometimes can be obtained with no change in hardware of current printers that are using a device-state error-diffusion algorithm such as presented in the present inventors' earlier patent document. As an example, FIG. 14 shows a portion of a halftoning table of sixteen by sixteen by sixteen (16.times.16.times.16=4,096) entries in accordance with the general principles of that earlier document--but restricted to a CMYK, i. e. four-ink, system.
For a related system, a three-ink (CMY) system operating at four passes for each region of the image, there will be about 5.sup.3 =125 device states available. A previous approach allows the device state "zero" (0), defined as OC, OM, OY, OK, to be used for any major entry in the halftoning table.
More specifically, each major entry chooses the closest device state. In this case, the device state "zero" is chosen for more than one hundred major entries. FIG. 14 shows the previous choice of cyan and magenta inkdrops for the layer of major entries 0.ltoreq.C.sub.i.ltoreq.15, 0.ltoreq.M.sub.i.ltoreq.15, Y.sub.i =0.
The present concern is the relatively grainy appearance that results from use of such a table, and in particular results in dot placements such as shown in FIG. 12 or 13. Particularly in highlight areas, where dots are scattered very sparsely overall, the overlapping or closely clustered cyan and magenta colorants appear as rather conspicuous dark dots.
The concern, however, also encompasses avoiding a similarly grainy appearance by avoiding deposition of cyan and magenta dots close together in a region where the amount of cyan and magenta is small. Such a region is not precisely the same as a "highlight region".
A highlight, by usual definition, is a region where there is very little color--mostly just white paper with a minor scattering of dots. As will be seen, however, this effect is also important in saturated-yellow regions.
9. Conclusion
Thus relative graininess of gray and near-gray features in highlight or near-yellow areas has continued to impede achievement of uniformly excellent inkjet printing--at high throughput--on all industrially important printing media. Thus important aspects of the technology used in the field of the invention remain amenable to useful refinement.